package com.sheng.leetcode.year2025.month09.day18;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author by ls
 * @date 2025/9/18
 * <p>
 * 3408. 设计任务管理器<p>
 * <p>
 * 一个任务管理器系统可以让用户管理他们的任务，每个任务有一个优先级。这个系统需要高效地处理添加、修改、执行和删除任务的操作。<p>
 * 请你设计一个 TaskManager 类：<p>
 * TaskManager(vector<vector<int>>& tasks) 初始化任务管理器，初始化的数组格式为 [userId, taskId, priority] ，表示给 userId 添加一个优先级为 priority 的任务 taskId 。<p>
 * void add(int userId, int taskId, int priority) 表示给用户 userId 添加一个优先级为 priority 的任务 taskId ，输入 保证 taskId 不在系统中。<p>
 * void edit(int taskId, int newPriority) 更新已经存在的任务 taskId 的优先级为 newPriority 。输入 保证 taskId 存在于系统中。<p>
 * void rmv(int taskId) 从系统中删除任务 taskId 。输入 保证 taskId 存在于系统中。<p>
 * int execTop() 执行所有用户的任务中优先级 最高 的任务，如果有多个任务优先级相同且都为 最高 ，执行 taskId 最大的一个任务。执行完任务后，taskId 从系统中 删除 。同时请你返回这个任务所属的用户 userId 。如果不存在任何任务，返回 -1 。<p>
 * 注意 ，一个用户可能被安排多个任务。<p>
 * <p>
 * 示例 1：<p>
 * 输入：<p>
 * ["TaskManager", "add", "edit", "execTop", "rmv", "add", "execTop"]<p>
 * [[[[1, 101, 10], [2, 102, 20], [3, 103, 15]]], [4, 104, 5], [102, 8], [], [101], [5, 105, 15], []]<p>
 * 输出：<p>
 * [null, null, null, 3, null, null, 5]<p>
 * 解释：<p>
 * TaskManager taskManager = new TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]]); // 分别给用户 1 ，2 和 3 初始化一个任务。<p>
 * taskManager.add(4, 104, 5); // 给用户 4 添加优先级为 5 的任务 104 。<p>
 * taskManager.edit(102, 8); // 更新任务 102 的优先级为 8 。<p>
 * taskManager.execTop(); // 返回 3 。执行用户 3 的任务 103 。<p>
 * taskManager.rmv(101); // 将系统中的任务 101 删除。<p>
 * taskManager.add(5, 105, 15); // 给用户 5 添加优先级为 15 的任务 105 。<p>
 * taskManager.execTop(); // 返回 5 。执行用户 5 的任务 105 。<p>
 * <p>
 * 提示：<p>
 * 1 <= tasks.length <= 10^5<p>
 * 0 <= userId <= 10^5<p>
 * 0 <= taskId <= 10^5<p>
 * 0 <= priority <= 10^9<p>
 * 0 <= newPriority <= 10^9<p>
 * add ，edit ，rmv 和 execTop 的总操作次数 加起来 不超过 2 * 10^5 次。<p>
 * 输入保证 taskId 是合法的。<p>
 */
public class LeetCode3408 {

    @Test
    public void test() {
        int[][] ints = {{1, 101, 10}, {2, 102, 20}, {3, 103, 15}};
        //二维数组转换成集合
        List<List<Integer>> tasks = Arrays.stream(ints).map(i -> Arrays.stream(i)
                        .boxed()
                        .collect(Collectors.toList())
                )
                .collect(Collectors.toList());
        // 分别给用户 1 ，2 和 3 初始化一个任务。
        TaskManager taskManager = new TaskManager(tasks);
        // 给用户 4 添加优先级为 5 的任务 104 。
        taskManager.add(4, 104, 5);
        // 更新任务 102 的优先级为 8 。
        taskManager.edit(102, 8);
        // 返回 3 。执行用户 3 的任务 103 。
        System.out.println(taskManager.execTop());
        // 将系统中的任务 101 删除。
        taskManager.rmv(101);
        // 给用户 5 添加优先级为 15 的任务 105 。
        taskManager.add(5, 105, 15);
        // 返回 5 。执行用户 5 的任务 105 。
        System.out.println(taskManager.execTop());
    }
}

class TaskManager {
    // taskId -> (priority, userId)
    private final Map<Integer, int[]> mp = new HashMap<>();

    // (priority, taskId, userId)
    private final PriorityQueue<int[]> pq =
            new PriorityQueue<>((a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);

    public TaskManager(List<List<Integer>> tasks) {
        for (List<Integer> task : tasks) {
            add(task.get(0), task.get(1), task.get(2));
        }
    }

    public void add(int userId, int taskId, int priority) {
        mp.put(taskId, new int[]{priority, userId});
        pq.offer(new int[]{priority, taskId, userId});
    }

    public void edit(int taskId, int newPriority) {
        // 懒修改
        // mp 修改的时候直接根据 key 增加就能直接覆盖，不需要额外的删除
        int userId = mp.get(taskId)[1];
        // 队列不进行修改，只做增量操作
        add(userId, taskId, newPriority);
    }

    public void rmv(int taskId) {
        // 懒删除
        mp.get(taskId)[0] = -1;
        // 队列不进行删除，只做增量操作
    }

    public int execTop() {
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int priority = top[0], taskId = top[1], userId = top[2];
            int[] p = mp.get(taskId);
            // 队列因为不进行修改，所以数据准确度以 mp 为准，不一致时认为是错误数据，跳过处理
            if (p[0] == priority && p[1] == userId) {
                rmv(taskId);
                return userId;
            }
            // else 货不对板，堆顶和 mp 中记录的不一样，说明堆顶数据已被修改或删除，不做处理
        }
        return -1;
    }
}

// 超时
//class TaskManager {
//
//    //    private TreeSet<Map.Entry<Integer, Integer>> taskSet;
//    private PriorityQueue<int[]> taskQueue;
//
//    private Map<Integer, Integer> map;
//
//    /**
//     * 初始化任务管理器，初始化的数组格式为 [userId, taskId, priority] ，表示给 userId 添加一个优先级为 priority 的任务 taskId 。
//     *
//     * @param tasks 初始化的数组
//     */
//    public TaskManager(List<List<Integer>> tasks) {
//        // 初始化
//        // 一个集合存储 key：taskId，value：userId-priority
//        map = new HashMap<>();
//        // 一个集合存储 key：priority，value：taskId
//        taskQueue = new PriorityQueue<>((task1, task2) -> {
//            // 先按优先级排序，优先级相同则按任务ID排序
//            int priorityComparison = Integer.compare(task2[2], task1[2]);
//            if (priorityComparison != 0) {
//                return priorityComparison;
//            } else {
//                return Integer.compare(task2[1], task1[1]);
//            }
//        });
//        for (List<Integer> task : tasks) {
//            // 将任务循环加入任务管理器中
//            add(task.get(0), task.get(1), task.get(2));
//        }
//    }
//
//    /**
//     * 给用户 userId 添加一个优先级为 priority 的任务 taskId ，输入 保证 taskId 不在系统中。
//     *
//     * @param userId   用户
//     * @param taskId   任务
//     * @param priority 优先级
//     */
//    public void add(int userId, int taskId, int priority) {
//        // 新增
//        map.put(taskId, userId);
//        taskQueue.offer(new int[]{priority, taskId});
//    }
//
//    /**
//     * 更新已经存在的任务 taskId 的优先级为 newPriority 。输入 保证 taskId 存在于系统中。
//     *
//     * @param taskId      任务
//     * @param newPriority 新的优先级
//     */
//    public void edit(int taskId, int newPriority) {
//        // 修改任务优先级
//        int[] poll = taskQueue.poll();
//        taskQueue.offer(new int[]{newPriority, taskId});
//    }
//
//    /**
//     * 从系统中删除任务 taskId 。输入 保证 taskId 存在于系统中。
//     *
//     * @param taskId 任务
//     */
//    public void rmv(int taskId) {
//        // 删除
//        map.remove(taskId);
//        taskSet.removeIf(task -> task.getValue().equals(taskId));
//    }
//
//    /**
//     * 执行所有用户的任务中优先级 最高 的任务，如果有多个任务优先级相同且都为 最高 ，
//     * 执行 taskId 最大的一个任务。执行完任务后，taskId 从系统中 删除 。
//     * 同时请你返回这个任务所属的用户 userId 。如果不存在任何任务，返回 -1 。
//     * 注意 ，一个用户可能被安排多个任务。
//     *
//     * @return 优先级 最高 的任务所属的用户 userId
//     */
//    public int execTop() {
//        // 要求需要可以获取到优先级从大到小进行排序，每个优先级可以对应多个任务，其中的任务 id 也需要从大到小排序，这个唯一
//        // 每个任务对应一个用户
//        if (taskSet.isEmpty()) {
//            return -1;
//        }
//        Integer taskId = taskSet.first().getValue();
//        Integer userId = map.get(taskId);
//        taskSet.removeIf(task -> task.getValue().equals(taskId));
//        map.remove(taskId);
//        return userId;
//    }
//}

/**
 * Your TaskManager object will be instantiated and called as such:
 * TaskManager obj = new TaskManager(tasks);
 * obj.add(userId,taskId,priority);
 * obj.edit(taskId,newPriority);
 * obj.rmv(taskId);
 * int param_4 = obj.execTop();
 */
